﻿//判断一个链表是否回文
bool isPail(ListNode* head) {
    vector<int> ret;
    while (head)
    {
        ret.push_back(head->val);
        head = head->next;
    }
    vector<int>tmp = ret;
    reverse(tmp.begin(), tmp.end());
    for (int i = 0;i < ret.size();i++) {
        if (ret[i] != tmp[i])
            return false;
    }
    return true;
}
//二叉树中的和为某一值的路径（求路径个数）
int count = 0;
void dfs(TreeNode* root, int num) {
    if (!root)return;
    if (root->val == num)
        count++;
    dfs(root->left, num - root->val);
    dfs(root->right, num - root->val);
}
void sum_count(TreeNode* root, int sum) {
    if (!root)return;
    dfs(root, sum);
    sum_count(root->left, sum);
    sum_count(root->right, sum);
}
int FindPath(TreeNode* root, int sum) {
    if (!root)return 0;
    sum_count(root, sum);
    return count;
}

//坏的苹果
int rotApple(vector<vector<int> >& grid) {
    // write code here
    int ret = 0;//次数
    vector<pair<int, int>> dir = { {-1,0},{1,0},{0,-1},{0,1} };
    int n = grid.size();//行
    int m = grid[0].size();//列
    queue<pair<int, int>>q;
    int count = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            if (grid[i][j] == 1)
                count++;
            if (grid[i][j] == 2)
                q.push(make_pair(i, j));
        }
    }
    while (!q.empty()) {
        int nur = q.size();
        bool flat = false;
        for (int i = 0;i < nur;i++) {
            auto x = q.front();
            q.pop();
            for (auto cur : dir) {
                int a = x.first + cur.first;
                int b = x.second + cur.second;
                if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1)
                {
                    grid[a][b] = 2;
                    q.push(make_pair(a, b));
                    count--;
                    flat = true;
                }
            }
        }
        if (flat)ret++;
    }
    return count ? -1 : ret;
}

//字符串计数
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string s1, s2;
    int len1, len2;

    // 读取输入
    while (std::cin >> s1 >> s2 >> len1 >> len2) {
        std::vector<int> res(len2, 0);
        int k = 0;

        // 找到第一个不同的字符位置
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] != s2[i]) {
                k = i;
                break;
            }
        }

        res[k] = s2[k] - s1[k];

        for (int i = k + 1; i < len2; ++i) {
            int temp = (res[i - 1] - 1) * 26;
            if (i < s1.size()) {
                temp += 'z' - s1[i];
            }
            else {
                temp += 26;
            }
            if (i < s2.size()) {
                temp += s2[i] - 'a';
            }
            else {
                temp += 26;
            }
            res[i] = temp;
        }

        int sum = 0;
        for (int i = len1 - 1; i < len2; ++i) {
            sum += res[i];
            sum %= 1000007;  // Avoid overflow by taking mod in every addition
        }

        std::cout << sum << std::endl;
    }

    return 0;
}



//最长公共子序列
#include <iostream>
#include<vector>
using namespace std;
int longest(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++) {
        char c1 = text1.at(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.at(j - 1);
            if (c1 == c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    string s1, s2;
    while (cin >> s1 >> s2) {
        int ret = 0;
        ret = longest(s1, s2);
        cout << ret << endl;
    }
    return 0;
}

//发邮件
#include <iostream>
using namespace std;

int main() {
    long long ret[21] = { 0,0,1 };
    for (int i = 3;i < 21;i++) {
        ret[i] = (i - 1) * (ret[i - 1] + ret[i - 2]);
    }
    int n;
    while (cin >> n) {
        cout << ret[n] << endl;
    }
    return 0;
}

//最长上升子序列
#include <iostream>
#include<vector>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
    int ret = 1;
    int n = nums.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j])
                dp[i] = max(dp[j] + 1, dp[i]);
        }
        ret = max(ret, dp[i]);
    }
    return ret;
}
int main() {
    int n;
    while (cin >> n) {
        vector<int> num(n);
        for (int i = 0;i < n; i++) {
            cin >> num[i];
        }
        int ret = 1;
        ret = lengthOfLIS(num);
        cout << ret << endl;
    }
    return 0;
}

//五子棋
#include <iostream>
using namespace std;
#include <vector>
#include <string>
bool func(string  s[]) {
    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 20; ++j) {
            int right = 1, right_down = 1, down = 1, left_down = 1;
            for (int t = 1; t < 5; t++) {
                if (s[i][j] == '.')
                    continue;
                if (j < 16 && s[i][j] == s[i][j + t])
                    right++;
                if (i < 16 && j < 16 && s[i][j] == s[i + t][j + t])
                    right_down++;
                if (i < 16 && s[i][j] == s[i + t][j])
                    down++;
                if (j > 4 && i < 16 && s[i][j] == s[i + t][j - t])
                    left_down++;
            }
            if (right == 5 || right_down == 5 || down == 5 || left_down == 5)
                return true;
        }
    }
    return false;
}

int main() {
    string s[20];
    while (cin >> s[0]) {
        for (int i = 1; i < 20; ++i)
            cin >> s[i];

        cout << (func(s) ? "Yes" : "No") << endl;
    }
    return 0;
}

//Emacs计算器
#include <iostream>
using namespace std;
#include <string>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <sstream>

int f(string s) {
    stringstream ss;
    ss << s;
    int num;
    ss >> num;
    return num;
}

int main() {
    int n;
    while (cin >> n) {
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            string x;
            cin >> x;
            if (x == "+") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();

                num1 += num2;
                st.push(num1);
            }
            else if (x == "-") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();

                num2 -= num1;
                st.push(num2);
            }
            else if (x == "*") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();

                num1 *= num2;
                st.push(num1);
            }
            else if (x == "/") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();

                num2 /= num1;
                st.push(num2);
            }
            else {
                int num = f(x);
                st.push(num);
            }
        }
        cout << st.top() << endl;
    }
    return 0;
}

//解读密码
#include <iostream>
#include<string>
using namespace std;

int main() {
    string str;
    while (getline(cin, str)) {
        for (int i = 0;i < str.size();i++) {
            if (str[i] >= '0' && str[i] <= '9')
                cout << str[i];
        }
        cout << endl;
    }
    return 0;
}

//走迷宫
#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
using namespace std;

vector<string> maze(10, string());

//ans存放最短路径，cur存放当前路径
void FindLeastSteps(int x, int y, int& ans, int cur)
{
    if (x > 9 || y > 9 || x < 0 || y < 0 || maze[x][y] != '.')
        return;
    //这个地方的剪枝很关键!!! 在路径很多的时候，可以有效的防止多余的计算
    if (cur > ans)
        return;
    //存储最短路径
    if (x == 9 && y == 8)
    {
        if (ans > cur)
            ans = cur;
        return;
    }
    //我们将x,y走过的路径的位置变为1，
    //这样就不用再开辟一个额外的used数组去记录已经走的路了
    maze[x][y] = 1;
    FindLeastSteps(x, y + 1, ans, cur + 1);
    FindLeastSteps(x + 1, y, ans, cur + 1);
    FindLeastSteps(x, y - 1, ans, cur + 1);
    FindLeastSteps(x - 1, y, ans, cur + 1);

    //回到上层递归时，要把当前所在位置重新设为'.' 代表没走这个位置
    maze[x][y] = '.';
}

int main()
{
    string s;
    int i = 0;
    while (getline(cin, s))
    {
        maze[i++] = s;
        if (i == 10)
        {
            int ans = INT_MAX;
            FindLeastSteps(0, 1, ans, 0);
            cout << ans << endl;
            i = 0;
        }
    }
    return 0;
}

//电话号码
#include <iostream>
#include<string>
#include<set>
using namespace std;
string AtoS(string a, const string num) {
    string ret;
    for (int i = 0;i < a.size();i++) {
        if (a[i] >= '0' && a[i] <= '9') {
            ret += a[i];
        }
        else if (a[i] == '-') {
            continue;
        }
        else {
            char b = num[a[i] - 'A'];
            ret += b;
        }
    }
    string x = ret.substr(0, 3);
    string y = ret.substr(3, 4);
    ret = "";
    ret += x;
    ret.push_back('-');
    ret += y;
    return ret;
}
int main() {
    string num = "222333444555666777788899991234567890";
    int n;
    while (cin >> n) {
        set<string>data;
        for (int i = 0; i < n; i++) {
            string a;
            cin >> a;
            string s = AtoS(a, num);
            data.insert(s);
        }
        for (auto c : data) {
            cout << c << endl;
        }
        cout << endl;
    }
    return 0;
}

//求和
#include <iostream>
#include <vector>
using namespace std;
void putsum(int n, int m, vector<int>& arr, int t) {
    if (m == 0) {
        for (int i = 0;i < arr.size();i++) {
            if (i == 0)
                cout << arr[i];
            else
                cout << " " << arr[i];
        }
        cout << endl;
    }
    for (int j = t;j <= n && j <= m;j++) {
        arr.push_back(j);
        putsum(n, m - j, arr, j + 1);
        arr.pop_back();
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> arr;
        putsum(n, m, arr, 1);
    }
    return 0;
}

//骆驼命名法
#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    while (cin >> str) {
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '_')continue;
            if (i > 0 && str[i - 1] == '_') {
                cout << (char)toupper(str[i]);
            }
            else
                cout << str[i];
        }
        cout << endl;
    }
    return 0;
}

//单词倒排
#include <iostream>
#include<string>
#include<vector>
#include<sstream>
using namespace std;

int main() {
    string str;
    vector<string> strs;
    while (getline(cin, str)) {
        for (int i = 0; i < str.size(); i++) {
            if (str[i] < 'a' && str[i] > 'Z') {
                str[i] = ' ';
            }
        }
        stringstream stream(str);
        while (stream >> str) {
            strs.push_back(str);
        }
        for (int i = strs.size() - 1; i > 0; i--) {
            cout << strs[i] << " ";
        }
        cout << strs[0];
    }
    return 0;
}

//乒乓球筐
#include <iostream>
#include<string>
using namespace std;

int main() {
    int A[26] = { 0 };
    int B[26] = { 0 };
    string str1, str2;
    while (cin >> str1 >> str2) {
        if (str1.size() < str2.size())
            cout << "No" << endl;
        for (int i = 0; i < str1.size(); i++)
            if (str1[i] >= 'A' && str1[i] <= 'Z')
                A[str1[i] - 'A']++;
        for (int i = 0; i < str2.size(); i++)
            if (str2[i] >= 'A' && str2[i] <= 'Z')
                B[str2[i] - 'A']++;
        int flag = 1;
        for (int i = 0; i < 26; i++) {
            if (A[i] < B[i])
                flag = 0;
        }
        if (flag == 0)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    return 0;
}

//查找兄弟单词
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

bool isbrother(string s1, string s2) {  //查看是否是兄弟单词
    if (s1.length() == s2.length()) { //兄弟单词一定要长度相等
        if (s1 == s2) //不能是同一个
            return false;
        sort(s1.begin(), s1.end());  //对两个字符串按字符字典序排序
        sort(s2.begin(), s2.end());
        if (s1 == s2) //排序后一样才是改变位置能办到的
            return true;
    }
    return false;
}
int main() {
    int n;
    while (cin >> n) {
        vector<string> strs(n);
        for (int i = 0; i < n; i++) //输入n个字符串
            cin >> strs[i];
        string str;
        cin >> str; //字符串str
        int k;
        cin >> k;
        vector<string> brothers;
        for (int i = 0; i < n; i++) { //检查每个字符串是否是兄弟单词
            if (isbrother(str, strs[i]))
                brothers.push_back(strs[i]);
        }
        sort(brothers.begin(), brothers.end()); //对后续排序
        cout << brothers.size() << endl;
        if (brothers.size() >= k) //输出第k个
            cout << brothers[k - 1] << endl;
    }
    return 0;
}

//数组中出现次数超过一半的数字
#include <unordered_map>
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        unordered_map<int, int>hash;
        for (int num : numbers) {
            hash[num]++;
        }
        for (int num : numbers) {
            if (hash[num] > numbers.size() / 2)
                return num;
        }
        return 0;
    }
};

//简单错误记录
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Rcond {
    string s;
    int flag;
};
int main() {
    string str;
    vector<string> v;
    while (getline(cin, str)) {
        v.push_back(str);
    }
    vector<Rcond>ret;
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (v[i][j] == ' ') {
                Rcond recond;
                recond.flag = 0;
                string s = v[i].substr(j + 1, v[i].size() - 1 - j);
                string t;
                for (int k = 1; k <= 16; k++) {
                    if (v[i][j - k] != '\\')
                        t.insert(t.begin(), v[i][j - k]);
                    else
                        break;
                }
                recond.s = t + ' ' + s;
                recond.flag += 1;
                int x;
                for (x = 0; x < ret.size(); x++) {
                    if (ret[x].s == recond.s) {
                        ret[x].flag += 1;
                        break;
                    }
                }
                if (x == ret.size())
                    ret.push_back(recond);
                break;
            }
        }
    }
    if (ret.size() > 8)
        for (vector<Rcond>::iterator it = ret.end() - 8; it != ret.end(); it++)
            cout << it->s << " " << it->flag << endl;
    else
        for (vector<Rcond>::iterator it = ret.begin(); it != ret.end(); it++)
            cout << it->s << " " << it->flag << endl;
    return 0;
}

//合唱团
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = LLONG_MAX;
const int MINF = LLONG_MIN;

void solve(int n, int K, int d, vector<int>& arr) {
    vector<vector<ll>> dpMAX(n, vector<ll>(K + 1, 0)); // 最大值
    vector<vector<ll>> dpMIN(n, vector<ll>(K + 1,
        0)); // 最小值，由于存在负数，否则直接计算最大值即可

    for (int i = 0; i < n;
        ++i) { // 初始化k=1时，以当前元素结尾的最大最小值
        dpMAX[i][1] = arr[i];
        dpMIN[i][1] = arr[i];
    }

    ll ans = MINF;

    for (int i = 0; i < n; ++i) {
        for (int k = 2; k <= min(i + 1, K); ++k) {
            for (int j = max(0, i - d); j < i;
                ++j) { // 再坐标差值<=d的范围内更新
                dpMAX[i][k] = max( // 更新最大值
                    dpMAX[i][k], max(dpMAX[j][k - 1] * arr[i], dpMIN[j][k - 1] * arr[i])
                );

                dpMIN[i][k] = min( // 更新最小值
                    dpMIN[i][k], min(dpMAX[j][k - 1] * arr[i], dpMIN[j][k - 1] * arr[i])
                );

            }
        }
        ans = max(ans, dpMAX[i][K]); // 更新结果
    }
    cout << ans << endl;
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k, d;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    cin >> k >> d;
    solve(n, k, d, arr);
    return 0;
}

//马戏团
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    return a.first == b.first ? a.second > b.second : a.first < b.first;
}

int cal(vector<pair<int, int>>& nums, int n) {
    sort(nums.begin(), nums.end(), cmp);

    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i].second >= nums[j].second) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int res = 1;
    for (int i = 0; i < n; i++) {
        res = max(res, dp[i]);
    }

    return res;
}

int main() {
    int n;
    while (cin >> n) {
        vector<pair<int, int>> nums;
        int index, weight, height;
        for (int i = 0; i < n; i++) {
            cin >> index >> weight >> height;
            nums.push_back({ weight, height });
        }

        cout << cal(nums, n) << endl;
    }
    return 0;
}

//左右最值的最大差
class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        int maxVal = 0;
        for (auto& e : A) {
            maxVal = max(maxVal, e);
        }
        int minVal = min(A[0], A[n - 1]);
        return maxVal - minVal;
    }
};

//顺时针打印矩阵s
#include <vector>
class Printer {
public:
    vector<int> clockwisePrint(vector<vector<int> > mat, int n, int m) {
        vector<int>ret;
        int left = 0, right = m - 1, top = 0, down = n - 1;
        while (left <= right && top <= down) {
            for (int i = left; i <= right; i++) {
                ret.push_back(mat[top][i]);
            }
            for (int i = top + 1; i <= down; i++) {
                ret.push_back(mat[i][right]);
            }
            if (top != down) {
                for (int i = right - 1; i >= left; i--) {
                    ret.push_back(mat[down][i]);
                }
            }
            if (left != right) {
                for (int i = down - 1; i > top; i--) {
                    ret.push_back(mat[i][left]);
                }
            }
            left++;
            right--;
            top++;
            down--;
        }
        return ret;
    }
};





//3072. 将元素分配到两个数组中 II
class BinaryIndexedTree {
private:
    vector<int> tree;

public:
    BinaryIndexedTree(int n) : tree(n + 1) {}

    void add(int i) {
        while (i < tree.size()) {
            tree[i] += 1;
            i += i & -i;
        }
    }

    int get(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i &= i - 1;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sortedNums = nums;
        sort(sortedNums.begin(), sortedNums.end());
        unordered_map<int, int> index;
        for (int i = 0; i < n; ++i) {
            index[sortedNums[i]] = i + 1;
        }

        vector<int> arr1 = { nums[0] };
        vector<int> arr2 = { nums[1] };
        BinaryIndexedTree tree1(n), tree2(n);
        tree1.add(index[nums[0]]);
        tree2.add(index[nums[1]]);

        for (int i = 2; i < n; ++i) {
            int count1 = arr1.size() - tree1.get(index[nums[i]]);
            int count2 = arr2.size() - tree2.get(index[nums[i]]);
            if (count1 > count2 || (count1 == count2 && arr1.size() <= arr2.size())) {
                arr1.push_back(nums[i]);
                tree1.add(index[nums[i]]);
            }
            else {
                arr2.push_back(nums[i]);
                tree2.add(index[nums[i]]);
            }
        }

        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
        return arr1;
    }
};


//412.Fizz Buzz
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> answer;
        for (int i = 1; i <= n; i++) {
            string curr;
            if (i % 3 == 0) {
                curr　 += "Fizz";
            }
            if (i % 5 == 0) {
                curr += "Buzz";
            }
            if (curr.size() == 0) {
                curr += to_string(i);
            }
            answer.emplace_back(curr);
        }
        return answer;
    }
};


//204.计数质数
class Solution
{
public:
    int countPrimes(int n)
    {
        if (n < 2)
            return 0;

        bool prime[n];
        memset(prime, 1, sizeof(prime));
        prime[0] = false;
        prime[1] = false;

        for (int x = 2; x < n; x++)
        {
            if (prime[x] == true)
            {
                for (long long y = (long long)x * x; y < n; y += x)
                {
                    prime[y] = false;
                }
            }
        }

        int res = 0;
        for (int x = 2; x < n; x++)
        {
            if (prime[x] == true)
                res++;
        }
        return res;
    }
};


//3的幂
class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

//罗马数字转整数
class Solution {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ret = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ret -= value;
            }
            else {
                ret += value;
            }
        }
        return ret;
    }
};

//经此一役小红所向无敌
#include <iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll a, h, b, k;
int main() {
    cin >> a >> h >> b >> k;

    ll sum = 0;
    ll cnt1 = h / b;
    ll cnt2 = k / a;
    if (h % b != 0)
        cnt1++;
    if (k % a != 0)
        cnt2++;
    ll cnt = min(cnt1, cnt2);
    sum += cnt * (a + b);
    if (cnt1 == cnt2)
        cout << sum << endl;
    else if (cnt1 > cnt2) {
        sum += a * 10;
        cout << sum << endl;
    }
    else if (cnt1 < cnt2) {
        sum += b * 10;
        cout << sum << endl;
    }
    return 0;
}
//连续子数组最大和
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll>arr(n);
    for (int i = 0;i < n;i++)
        cin >> arr[i];
    vector<ll>dp(n, 0);
    dp[0] = arr[0];
    for (int i = 1;i < n;i++) {
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
    }
    ll ret = LONG_MIN;
    for (int i = 0;i < n;i++) {
        ret = max(dp[i], ret);
    }
    cout << ret << endl;
    return 0;
}
//非对称之美
#include <iostream>
#include <string>
using namespace std;
int n;
string s;
int fun() {
    // 1. 判断是否全都是相同字符
    bool flag = false;
    for (int i = 1; i < n; i++) {
        if (s[i] != s[0]) {
            flag = true;
            break;
        }
    }
    if (flag == false)
        return 0;
    // 2. 判断本⾝是否是回⽂
    flag = true;
    int left = 0, right = n - 1;
    while (left < right) {
        if (s[left] == s[right]) {
            left++;
            right--;
        }
        else {
            flag = false;
            break;
        }
    }
    if (flag)
        return n - 1;
    else
        return n;
}
int main() {
    cin >> s;
    n = s.size();
    cout << fun() << endl;
    return 0;
}

//爱丽丝的人偶
#include <iostream>
using namespace std;
int n;
int main() {
    cin >> n;
    int left = 1, right = n;
    while (left <= right) {
        cout << left << " ";
        left++;
        if (left <= right) {
            cout << right << " ";
            right--;
        }
    }
    return 0;
}
//集合
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int n1[N];
int n2[N];
int main() {
    cin >> n >> m;
    set<int> s;
    int x;
    for (int i = 0; i < n + m; ++i)
    {
        cin >> x;
        s.emplace(x);
    }
    for (int e : s)
        cout << e << ' ';
    cout << endl;
    return 0;
}
//最长回文子序列
#include <iostream>
using namespace std;

const int N = 1010;
int dp[N][N];
int main() {
    string s;
    cin >> s;
    int n = s.size();
    // 初始化
    dp[0][0] = dp[n - 1][n - 1] = 1;
    // 填表
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= n - 1; ++j) {
            if (i > j)
                dp[i][j] = 0;
            else if (i == j)
                dp[i][j] = 1;
            else {
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}

//添加字符
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s1;
    string s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    int ret = 0;
    if (n == m) {
        for (int i = 0;i < n;i++) {
            if (s1[i] != s2[i]) {
                ret++;
            }
        }
        cout << ret << endl;
    }
    else {
        int d = m - n;
        int maxn = 0;
        for (int i = 0;i <= d;i++) {
            maxn = 0;
            int j = 0;
            int k = i;
            while (j < n) {
                if (s1[j] == s2[k]) {
                    maxn++;
                }
                j++;
                k++;
            }
            ret = max(maxn, ret);
        }
        cout << n - ret << endl;
    }

    return 0;
}
//数组变换
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<ll> arr;
    int x;
    int maxx = 0;
    for (int i = 0;i < n;i++) {
        cin >> x;
        arr.push_back(x);
        maxx = max(maxx, x);//记录最大值
    }
    for (int i = 0;i < n;i++) {
        if (!((maxx / arr[i]) % 2 == 0 || maxx == arr[i])) {//是否可以通过*2变为最大值
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}
//装箱问题
#include <iostream>
using namespace std;

int V, n;
int v[20010];
int dp[40][20010];
int main() {
    cin >> V >> n;
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    // 填表
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i]);
        }
    }
    cout << V - dp[n][V] << endl;
    return 0;
}

//打怪
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int h, a, H, A;
        cin >> h >> a >> H >> A;
        if (a >= H) {
            cout << -1 << endl;
            continue;
        }
        int ret = 0;
        int tmp = H;
        while (h > 0) {
            tmp -= a;
            if (tmp > 0)
                h -= A;
            if (tmp <= 0) {
                ret++;
                tmp = H;
            }
        }
        cout << ret << endl;
    }
    return 0;
}
//字符串分类
#include <algorithm>
#include <iostream>
#include <string>
#include<unordered_set>
using namespace std;
string s;
int main() {
    int n;
    cin >> n;
    unordered_set<string> hash;
    while (n--) {
        cin >> s;
        sort(s.begin(), s.end());
        hash.insert(s);
    }
    cout << hash.size() << endl;
    return 0;
}
//城市群数量
vector<bool> vim(210);
class Solution {
public:
    // 检查连接的城市是否遍历完
    bool Check(int i) {
        for (int e : edges[i])
            if (vim[e] == false)
                return true;
        return false;
    }
    // DFS
    void f(unordered_map<int, vector<int>> edges, int i) {
        vim[i] = true;
        if (Check(i) == false)
            return;
        for (int e : edges[i]) {
            if (vim[e] == false) {
                f(edges, e);
            }
        }
    }

    // 建图
    unordered_map<int, vector<int>> edges;
    int citys(vector<vector<int> >& m) {
        int line = m.size();
        int col = m[0].size();
        for (int i = 0; i < line; ++i) {
            for (int j = 0; j < col; ++j) {
                if (m[i][j] == 1 && i != j) {
                    edges[i + 1].push_back(j + 1);
                }
            }
        }
        int cnt = 0;
        for (int i = 1; i <= line; ++i) {
            if (vim[i] == false) {
                cnt++;
                f(edges, i);
            }
        }
        return cnt;
    }
};

//判断是不是平衡⼆叉树
class Solution {
public:
    // 高度
    int hight(TreeNode* pRoot) {
        if (pRoot == nullptr)
            return 0;
        int l = hight(pRoot->left);
        int r = hight(pRoot->right);
        return max(l, r) + 1;
    }
    // 检查是否为平衡二叉树
    bool Check(TreeNode* pl, TreeNode* pr) {
        if (abs(hight(pl) - hight(pr)) <= 1)
            return true;
        return false;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (!pRoot)
            return true;
        if (Check(pRoot->left, pRoot->right))
            return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
        else
            return false;
    }
};
//最大子矩阵
#include <iostream>
using namespace std;
const int sta = 110;
int N;
int arr[sta][sta];
int sum[sta][sta];
int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            cin >> arr[i][j];
    // 构建前缀和
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
    // 枚举
    int ret = -127 * N;
    for (int x1 = 1; x1 <= N; ++x1)
        for (int y1 = 1; y1 <= N; ++y1)
            for (int x2 = x1; x2 <= N; ++x2)
                for (int y2 = y1; y2 <= N; ++y2)
                    if (ret < sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1])
                        ret = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    cout << ret << endl;
    return 0;
}
//小葱的01串
#include <iostream>
using namespace std;
int n;
int cnt[2];
string s;
int main() {
    cin >> n;
    cin >> s;

    int cnt0 = 0, cnt1 = 0;
    for (auto c : s) {
        if (c == '0')
            cnt0++;
        else
            cnt1++;
    }
    int l = 0, r = 0, ret = 0;
    int half = s.size() / 2;
    while (r < n - 1) {
        cnt[s[r] - '0']++;
        while (r - l + 1 > half) {
            cnt[s[l] - '0']--;
            l++;
        }
        if (r - l + 1 == half) {
            if (cnt[0] * 2 == cnt0 && cnt[1] * 2 == cnt1) {
                ret += 2;
            }
        }
        r++;
    }
    cout << ret << endl;
    return 0;
}

//笨小猴
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
bool isPrime(int n) {
    // 处理小于2的情况
    if (n <= 1) return false;
    // 2和3都是质数
    if (n <= 3) return true;
    // 排除能被2或3整除的数
    if (n % 2 == 0 || n % 3 == 0) return false;
    // 检查从5到sqrt(n)之间的所有奇数
    for (int i = 5; i <= sqrt(n); i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    string str;
    int hash[26] = { 0 };
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        hash[str[i] - 'a']++;
    }
    int maxn = INT_MIN;
    int minn = INT_MAX;
    for (int i = 0; i < 26; i++) {
        maxn = max(maxn, hash[i]);
        if (hash[i] != 0)
            minn = min(minn, hash[i]);
    }
    int ret = maxn - minn;
    if (isPrime(ret)) {
        cout << "Lucky Word" << endl;
        cout << ret << endl;
    }
    else {
        cout << "No Answer" << endl;
        cout << "0" << endl;
    }
    return 0;
}
//主持人调度
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param schedule int整型vector<vector<>>
     * @return bool布尔型
     */
    bool hostschedule(vector<vector<int> >& schedule) {
        int n = schedule.size();
        if (n <= 1)return true;
        sort(schedule.begin(), schedule.end());
        for (int i = 1; i < n;i++) {
            if (schedule[i][0] < schedule[i - 1][1])
                return false;
        }
        return true;
    }
};
//分割等和子集

//前缀和（错误）有部分测试用例不能通过
// #include <algorithm>
// #include <iostream>
// #include <vector>
// using namespace std;

// int main() {
//     int n;
//     cin>>n;
//     vector<int>arr(n);
//     for(int i = 0;i < n;i++){
//         cin>>arr[i];
//     }
//     sort(arr.begin(), arr.end());
//     vector<int> funsum(n);
//     funsum[0] = arr[0];
//     for(int i = 1;i < n;i++){
//         funsum[i] = funsum[i - 1] + arr[i];
//     }
//     for(int i = 0;i < n - 1;i++){
//         if(funsum[i] == funsum[n- 1] - funsum[i]){
//             cout<<"true"<<endl;
//             return 0;
//         }
//     }
//     cout<<"false"<<endl;
//     return 0;
// }
//动态规划
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
bool dp[501][501 * 101 / 2];
int main() {
    int n;
    cin >> n;
    vector<int>arr(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    if (sum % 2 != 0)cout << "false" << endl;
    else {
        // 初始化
        for (int i = 0; i <= n; ++i)
            dp[i][0] = true;
        int mid = sum / 2;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= mid; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= arr[i])
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i]];
            }
        }
        if (dp[n][mid]) cout << "true" << endl;
        else cout << "false" << endl;
    }


    return 0;
}

//小红的ABC
#include <iostream>
#include<string>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();
    int ret = -1;
    for (int i = 0; i < n; i++) {
        if (i + 1 < n && str[i] == str[i + 1]) {
            ret = 2;
            break;
        }
        if (i + 2 < n && str[i] == str[i + 2]) {
            ret = 3;
        }
    }
    cout << ret << endl;
    return 0;
}
//不相邻取数
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int n;
int arr[N];
int dp[N][2];
int main() {

    cin >> n;
    for (int i = 1;i <= n;i++)
        cin >> arr[i];
    dp[1][1] = arr[1];
    for (int i = 1;i <= n;i++)
    {
        dp[i][1] = dp[i - 1][0] + arr[i];
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
    }
    cout << max(dp[n][0], dp[n][1]) << endl;;
    return 0;
}
//空调遥控
#include <algorithm>
#include <iostream>
#include<vector>
using namespace std;

int main() {
    int n, p;
    cin >> n >> p;
    vector<int>t(n);
    for (int i = 0;i < n;i++)
        cin >> t[i];
    sort(t.begin(), t.end());
    int ret = 0;
    int r = 0, l = 0;
    while (r < n) {
        while (t[r] - t[l] > 2 * p)
            l++;
        if (t[r] - t[l] <= 2 * p)
            ret = max(ret, r - l + 1);
        r++;
    }
    cout << ret << endl;
    return 0;
}

//kotori和气球
#include <iostream>
using namespace std;

int n, m;
int main() {
    cin >> n >> m;
    int ret = n;
    for (int i = 1; i < m; ++i) {
        ret *= n - 1;
        if (ret > 109)
            ret %= 109;
    }
    cout << ret << endl;
    return 0;
}
//走迷宫
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
int x1, y1, x2, y2;
char arr[N][N];
int dist[N][N]; // [i, j] 位置是否已经搜索过，以及到达 [i, j] 位置的最短距离
int bfs() {
    if (arr[x2][y2] == '*') return -1;
    memset(dist, -1, sizeof dist); // 表⽰还没开始搜索
    queue<pair<int, int>> q;
    q.push({ x1, y1 });
    dist[x1][y1] = 0;
    while (q.size()) {
        auto [a, b] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] == '.' &&
                dist[x][y] == -1) {
                q.push({ x, y });
                dist[x][y] = dist[a][b] + 1;
                if (x == x2 && y == y2) return dist[x2][y2];
            }
        }
    }
    return -1;
}
int main() {
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}
//主持人调度（二）
class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end());
        // 创建⼀个⼩根堆
        priority_queue<int, vector<int>, greater<int>> heap;
        // 先把第⼀个区间放进去
        heap.push(startEnd[0][1]);
        // 处理剩下的区间
        for (int i = 1; i < n; i++) {
            int a = startEnd[i][0], b = startEnd[i][1];
            if (a >= heap.top()) { // 没有重叠
                heap.pop();
                heap.push(b);
            }
            else { // 有重叠
                heap.push(b); // 重新安排⼀个⼈
            }
        }
        return heap.size();
    }
};

//游游的重组偶数
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int keyi;
void solve() {
    int arr[10] = { 0 };
    int x;
    cin >> x;
    if (x % 2 == 0) {
        cout << x << endl;
        return;
    }
    int cnt = 0;
    int flag = 0;
    while (x) {
        arr[cnt++] = x % 10;
        x /= 10;
    }
    for (int i = 0; i < cnt; ++i) {
        if (arr[i] % 2 == 0) {
            keyi = i;
            flag = 1;
        }
    }
    if (flag == 0) {
        cout << -1 << endl;
        return;
    }

    string ret;
    for (int i = 0; i < cnt; ++i) {
        if (i != keyi) {
            ret += arr[i] + '0';
        }
    }
    ret += arr[keyi] + '0';
    cout << ret << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}
//体操队形
#include <iostream>
using namespace std;
const int N = 15;
int ret;
int n;
bool vis[N];
int arr[N];
void dfs(int pos) {
    if (pos == n + 1) { // 找到⼀种合法⽅案
        ret++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 当前 i 已经放过了 - 剪枝
        if (vis[arr[i]]) return; // 剪枝
        vis[i] = true; // 相当于放上 i 号队员
        dfs(pos + 1);
        vis[i] = false;
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    dfs(1);
    cout << ret << endl;
    return 0;
}
//二叉树中的最大路径和
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    int ret = -1001;
    int dfs(TreeNode* root) {
        if (root == nullptr)return 0;
        int l = max(0, dfs(root->left));
        int r = max(0, dfs(root->right));
        ret = max(ret, root->val + l + r);
        return root->val + max(l, r);

    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ret;
    }
};
//排序子序列
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int a[N];
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];
    int i = 1;
    int ret = 0;
    while (i <= n)
    {
        if (i == n)
        {
            ret++;
            break;
        }
        if (a[i] < a[i + 1])
        {
            ret++;
            while (i + 1 <= n && a[i] <= a[i + 1])
            {
                i++;
            }
        }
        else if (a[i] > a[i + 1])
        {
            ret++;
            while (i + 1 <= n && a[i] >= a[i + 1])
            {
                i++;
            }
        }
        else
        {
            while (i + 1 <= n && a[i] == a[i + 1])
            {
                i++;
            }
        }
        ++i;
    }
    cout << ret << endl;
    return 0;
}
//消减整数
#include <iostream>
using namespace std;

int t, h;
int solve()
{
    if (h == 1)
        return 1;
    int ret = 0;
    int a = 1;
    while (h)
    {
        h -= a;
        ret++;
        if (h % (2 * a) == 0)
            a *= 2;
    }
    return ret;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> h;
        cout << solve() << endl;
    }
    return 0;
}
//最长上升子序列(二)
class Solution
{
    int dp[100010] = { 0 }; // dp[i] 表⽰：⻓度为 i 的最⼩末尾
    int pos = 0;
public:
    int LIS(vector<int>& a)
    {
        for (auto x : a)
        {
            // 查找 x 应该放在哪个位置
            if (pos == 0 || x > dp[pos])
            {
                dp[++pos] = x;
            }
            else
            {
                // ⼆分查找插⼊位置
                int l = 1, r = pos;
                while (l < r)
                {
                    int mid = (l + r) / 2;
                    if (dp[mid] >= x) r = mid;
                    else l = mid + 1;
                }
                dp[l] = x;
            }
        }
        return pos;
    }
};
//爱吃素
#include <iostream>
using namespace std;
using ll = long long;

bool isprime(ll num) {
    if (num < 2)
        return false;
    for (ll i = 2; i * i <= num; i++)
        if (num % i == 0)
            return false;
    return true;
}
void fun() {
    ll a, b;
    cin >> a >> b;
    if ((isprime(a) && b == 1) || (isprime(b) && a == 1))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
int main() {
    int n;
    cin >> n;
    while (n--)
        fun();

    return 0;
}
//相差不超过k的最多数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k, ret;
int main() {
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a.begin() + 1, a.end());
    int l = 1, r = 1;
    while (r < n) {
        while (a[r] - a[l] > k && l <= n)
            l++;
        while (a[r] - a[l] <= k && r <= n)
            r++;
        ret = max(ret, r - l);
    }
    cout << ret << endl;
    return 0;
}
//最长公共子序列(一)
#include <iostream>
using namespace std;

const int N = 1010;
int dp[N][N];
char s1[N];
char s2[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> s1[i];
    for (int i = 1; i <= m; ++i) cin >> s2[i];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (s1[i] == s2[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n][m] << endl;
    return 0;
}
//小红的口罩
#include <iostream>
#include<functional>
#include<vector>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
priority_queue<int, vector<int>, greater<>>q;
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0;i < n;i++) {
        cin >> arr[i];
        q.push(arr[i]);
    }
    int sum = 0;
    int ret = 0;
    while (q.size()) {
        int a = q.top();
        q.pop();
        sum += a;
        if (sum <= k)
            ret++;
        else
            break;
        q.push(a * 2);
    }
    cout << ret << endl;
    return 0;
}
//春游
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, a, b;
        cin >> n >> a >> b;
        long long ret = 0;
        if (n <= 2) {
            ret = min(a, b);
        }
        else {
            if (a * 3 < b * 2) {
                ret += n / 2 * a;
                n %= 2;
                if (n == 1)
                    ret += min(min(a, b), b - a);
            }
            else {
                ret += n / 3 * b;
                n %= 3;
                if (n == 1)
                    ret += min(min(a, b), 2 * a - b);
                if (n == 2)
                    ret += min(min(a, b), 3 * a - b);
            }
        }
        cout << ret << endl;
    }
    return 0;
}
//数位染色
#include <iostream>
using namespace std;
int a[20];
bool dp[20][180];
int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; ++i)
        a[i + 1] = s[i] - '0';
    // 求和
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += a[i];
    // 特殊情况
    if (sum % 2 != 0)
        cout << "No" << endl;
    else {
        int mid = sum / 2;
        for (int i = 0; i <= n; ++i)
            dp[i][0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= mid; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j >= a[i])
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - a[i]];
            }
        }
        if (dp[n][mid])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
//素数回文
#include <iostream>
using namespace std;
using ll = long long;
bool Check(ll x) {
    if (x < 2)
        return false;
    for (ll i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}
ll my_stoi(string s) {
    ll sum = 0;
    for (ll i = s.size() - 1; i >= 0; --i)
        sum = sum * 10 + (s[i] - '0');
    return sum;
}
int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = n - 2; i >= 0; --i)
        s += s[i];
    ll tmp = my_stoi(s);
    if (Check(tmp))
        cout << "prime" << endl;
    else
        cout << "noprime" << endl;
    return 0;
}
//活动安排
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

using PII = pair<int, int>;
const int N = 2e5 + 10;
int n;
PII a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i].first >> a[i].second;
    sort(a, a + n);
    int ret = 1;
    int end = a[0].second;
    for (int i = 1; i < n; ++i) {
        if (a[i].first < end) {
            end = min(end, a[i].second);
        }
        else {
            ret++;
            end = a[i].second;
        }
    }
    cout << ret << endl;
    return 0;
}
//合唱团

//跳台阶扩展问题
#include <iostream>
using namespace std;
int dp[30];
int main() {
    int n;
    cin >> n;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= i - 1; j++)
        {
            dp[i] += dp[i - j];
        }
        dp[i] += 1;
    }
    cout << dp[n] << endl;
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    cout << (1 << (n - 1)) << endl;
    return 0;
}
//包含不超过两种字符的最长子串
#include <iostream>
#include <iterator>
using namespace std;

int a[26];
int main() {
    string s;
    cin >> s;

    int cnt = 0, ret = 0;
    int l = 0, r = 0, n = s.size();
    while (r < n)
    {
        if (a[s[r] - 'a']++ == 0)
            cnt++;

        while (cnt > 2)
            if (a[s[l++] - 'a']-- == 1)
                cnt--;

        ret = max(ret, r - l + 1);
        r++;
    }
    cout << ret << endl;
    return 0;
}
//字符串的排列
class Solution {
public:
    int n;
    string s;
    string tmp;
    bool vis[11] = { false };
    vector<string> ret;

    void DFS(int pos)
    {
        if (pos == n)
        {
            ret.push_back(tmp);
            return;
        }

        for (int i = 0; i < n; ++i)
        {
            if (!vis[i])
            {
                if (i - 1 >= 0 && s[i] == s[i - 1] && !vis[i - 1])
                    continue;// 剪枝

                tmp.push_back(s[i]);
                vis[i] = true;

                // 递归
                DFS(pos + 1);

                // 回溯
                tmp.pop_back();
                vis[i] = false;
            }
        }
    }

    vector<string> Permutation(string str) {
        s = str;
        n = str.size();
        sort(s.begin(), s.end());

        DFS(0);
        return ret;
    }
};
//ISBN号码
#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    int sum = 0;
    int k = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] != '-') {
            sum += (s[i] - '0') * k;
            ++k;
        }
    }
    sum %= 11;
    if (sum == 10 && s[n - 1] == 'X' || sum == (s[n - 1] - '0'))
        cout << "Right" << endl;
    else {
        for (int i = 0; i < n - 1; ++i)
            cout << s[i];
        if (sum == 10)
            cout << 'X';
        else
            cout << sum;
    }
    return 0;
}
//kotori和迷宫
// BFS
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 35;
int x1, y1; // 标记起点位置
int n, m;
char arr[N][N];
int dist[N][N];
queue<pair<int, int>> q;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
void bfs() {
    memset(dist, -1, sizeof dist);
    dist[x1][y1] = 0;
    q.push({ x1, y1 });

    while (q.size()) {
        auto [x2, y2] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = x2 + dx[i], b = y2 + dy[i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && dist[a][b] == -1 &&
                arr[a][b] != '*') {
                dist[a][b] = dist[x2][y2] + 1;
                if (arr[a][b] != 'e') {
                    q.push({ a, b });
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'k') {
                x1 = i, y1 = j;
            }
        }
    }
    bfs();
    int count = 0, ret = 1e9;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == 'e' && dist[i][j] != -1) {
                count++;
                ret = min(ret, dist[i][j]);
            }
        }
    }
    if (count == 0) cout << -1 << endl;
    else cout << count << " " << ret << endl;

    return 0;
}
//矩阵最长递增路径
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    const static int N = 1010;
    bool vis[N][N] = { false };
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int n, m, ret = 0;
    vector<vector<int>> arr;
    bool Check(int x, int y) {
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && arr[x][y] < arr[a][b])
                return true;
        }
        return false;
    }
    void DFS(int x, int y, int d) {
        if (!Check(x, y)) {
            ret = max(ret, d);
            return;
        }

        vis[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && !vis[a][b] && arr[x][y] < arr[a][b]) {
                DFS(a, b, d + 1);
            }
        }
        vis[x][y] = false;
    }
    int solve(vector<vector<int>>& matrix) {
        arr = matrix;
        n = matrix.size();
        m = matrix[0].size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                DFS(i, j, 0);
        return ret + 1;
    }
};
//奇数位丢弃
#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v;
    int n;
    while (cin >> n)
    {
        v.clear();
        for (int i = 0; i <= n; ++i)
            v.push_back(i);

        while (v.size() > 1)
        {
            auto it = v.begin();
            while (it < v.end())
            {
                it = v.erase(it);
                if (it != v.end())
                    it++;
            }
        }
        cout << v[0] << endl;
    }
    return 0;
}
//求和
#include <iostream>
using namespace std;
int n, m;
bool vis[11];
int path;// 存储走过的路径和
void DFS(int pos)
{
    if (path == m)
    {
        for (int i = 1; i <= n; ++i)
            if (vis[i])
                cout << i << ' ';
        cout << endl;
        return;
    }
    if (path > m || pos > n) return;
    // 选pos
    path += pos;
    vis[pos] = true;
    DFS(pos + 1);
    path -= pos;
    vis[pos] = false;
    // 不选pos
    DFS(pos + 1);
}
int main()
{
    cin >> n >> m;
    DFS(1);
    return 0;
}
//计算字符串的编辑距离
#include <iostream>
#include <string>
using namespace std;
const int N = 1010;
int dp[N][N];
char a[N];
char b[N];
int main() {
    string s1;
    string s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    // 填入char数组中，为了让下标从 1 开始
    for (int i = 1; i <= n; ++i)
        a[i] = s1[i - 1];
    for (int i = 1; i <= m; ++i)
        b[i] = s2[i - 1];
    // 初始化
    for (int i = 1; i <= n; ++i)
        dp[i][0] = i;
    for (int j = 1; j <= m; ++j)
        dp[0][j] = j;
    // 填表
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
        }
    }
    // 返回
    cout << dp[n][m] << endl;
    return 0;
}
//提取不重复的数
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    int hash[10] = { 0 };
    string s;
    while (n > 0) {
        int t = n % 10;
        n /= 10;
        if (hash[t] == 0)
            s += t + '0';
        hash[t]++;
    }
    int ret = stoi(s);
    cout << ret << endl;
    return 0;
}
//哈弗曼编码
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
long long sum = 0;
typedef struct tree {
    long long val;
    tree* left = NULL;
    tree* right = NULL;
    tree* parent = NULL;
} tree;
struct cmp {
    bool operator()(tree* a, tree* b) const {
        return a->val > b->val;
    }
};
int getSum(tree* root, int deep) {
    if (root->left == NULL && root->right == NULL) {
        sum += deep * root->val;
        return 0;
    }
    if (root->left) {
        getSum(root->left, deep + 1);
    }
    if (root->right) {
        getSum(root->right, deep + 1);
    }
    return 0;


}

int main() {
    int n;
    cin >> n;
    priority_queue<tree*, vector<tree*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        tree* t = new tree;
        cin >> t->val;
        pq.push(t);
    }
    while (1) {
        if (pq.size() == 1) {
            break;
        }
        tree* now = new tree;
        tree* a = pq.top();
        pq.pop();
        tree* b = pq.top();
        pq.pop();
        now->val = a->val + b->val;
        now->left = a;
        now->right = b;
        pq.push(now);
    }
    getSum(pq.top(), 0);
    cout << sum;
    return 0;
}
//abb
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    char s[n];
    for (int i = 0;i < n;i++) {
        cin >> s;
    }
    int fro[26] = { 0 };
    int dou[26] = { 0 };
    long long ret = 0;
    for (int i = 0;i < n;i++) {
        int x = s[i] - 'a';
        ret += fro[x];

        fro[x] = fro[x] + i - dou[x];
        dou[x] = dou[x] + 1;
    }
    cout << ret << endl;
    return 0;
}
//旋转字符串
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转字符串
     * @param A string字符串
     * @param B string字符串
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        if (A.size() != B.size())return false;
        else {
            string str = A + A;
            return str.find(B) != -1;
        }
    }
};
//合并k个有序链表
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> s;
        for (int i = 0; i < lists.size(); i++) {
            ListNode* tmp = lists[i];
            while (tmp != nullptr) {
                s.push_back(tmp->val);
                tmp = tmp->next;
            }
        }
        sort(s.begin(), s.end());
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        for (int i = 0; i < s.size(); i++) {
            ListNode* tmp = new ListNode(s[i]);
            cur->next = tmp;
            cur = cur->next;
        }
        return head->next;
    }
};
//滑雪
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int arr[N][N];
int dp[N][N];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int dfs(int i, int j) {
    if (dp[i][j])
        return dp[i][j];
    int len = 1;
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] < arr[i][j]) {
            len = max(len, 1 + dfs(x, y));
        }
    }
    dp[i][j] = len;
    return len;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    int ret = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ret = max(ret, dfs(i, j));
        }
    }
    cout << ret << endl;
    return 0;
}
//天使果冻
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0;i < n;i++)
        cin >> arr[i];
    int dp[n];
    dp[0] = arr[0];
    dp[1] = min(arr[1], dp[0]);
    int max_i = max(arr[1], dp[0]);
    for (int i = 2;i < n;i++) {
        if (arr[i] > dp[i - 1] && arr[i] < max_i) {
            dp[i] = arr[i];
        }
        else if (arr[i] < dp[i - 1]) {
            dp[i] = dp[i - 1];
        }
        else if (arr[i] >= max_i) {
            dp[i] = max_i;
            max_i = arr[i];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int ret = dp[x - 1];
        cout << ret << endl;
    }
    return 0;
}
//dd爱旋转
#include <iostream>
using namespace std;

const int N = 1010;
int n;
int g[N][N];
void setRow() { // ⾏对称
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            swap(g[i][j], g[n - 1 - i][j]);
        }
    }
}
void setCol() { // 列对称
    for (int j = 0; j < n / 2; j++) {
        for (int i = 0; i < n; i++) {
            swap(g[i][j], g[i][n - 1 - j]);
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    int q, x;
    cin >> q;

    int row = 0, col = 0;
    while (q--) {
        cin >> x;
        if (x == 1) row++, col++;
        else row++;
    }
    row %= 2;
    col %= 2;
    if (row)
        setRow();
    if (col)
        setCol();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
//小红取数
#include <iostream>
using namespace std;
using ll = long long;
int n, k;
ll a[1010];
ll dp[1010][1010];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= k; ++i)
        dp[0][i] = -1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (dp[i - 1][(j - a[i] % k + k) % k] != -1)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - a[i] % k + k) % k] + a[i]);
        }
    }
    if (dp[n][0] <= 0)
        cout << -1 << endl;
    else
        cout << dp[n][0] << endl;
    return 0;
}
//神奇的字符（二）
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    int hash[26] = { 0 };
    while (getline(cin, str)) {
        for (auto c : str) {
            if (c != ' ')
                hash[c - 'a']++;
        }
    }
    char ret;
    int max_i = hash[0];
    int x = 0;
    for (int i = 1;i < 26;++i) {
        if (hash[i] > max_i) {
            max_i = hash[i];
            x = i;
        }
    }
    ret = 'a' + x;
    cout << ret << endl;
    return 0;
}
//字符编码
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        int ret = 0;
        int cnt[250] = { 0 };
        for (auto c : s)
            cnt[c]++;
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int n : cnt)
            if (n != 0)
                pq.push(n);

        while (pq.size() != 1) {
            int top1 = pq.top();
            pq.pop();
            int top2 = pq.top();
            pq.pop();
            ret += (top1 + top2);
            pq.push(top1 + top2);
        }
        cout << ret << endl;
    }
    return 0;
}
//最少的完全平方数
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int arr[110];
int dp[110][10010];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= 100; ++i)
        arr[i] = i * i;
    int r = sqrt(n);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= r; ++i)
        dp[i][0] = 0;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= arr[i])
                dp[i][j] = min(dp[i - 1][j], dp[i][j - arr[i]] + 1);
        }
    }
    cout << dp[r][n] << endl;
    return 0;
}
//游游的字母串
#include <climits>
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int ret = INT_MAX;
    for (char ch = 'a'; ch <= 'z'; ch++) {
        int sum = 0;
        for (auto x : s) {
            sum += min(abs(x - ch), 26 - abs(x - ch));
        }
        ret = min(ret, sum);
    }
    cout << ret << endl;

    return 0;
}
//体育课测验（二）
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numProject int整型
     * @param groups int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> findOrder(int numProject, vector<vector<int> >& groups) {
        int n = numProject;
        unordered_map<int, vector<int>> edges;
        vector<int> ret;
        queue<int> q;
        int in[2010] = { 0 };
        // 建图
        for (auto e : groups) {
            edges[e[1]].push_back(e[0]);
            in[e[0]]++;
        }
        // 将入度为0的点加入队列中
        for (int i = 0; i < n; ++i)
            if (in[i] == 0)
                q.push(i);
        // 开始拓扑排序
        while (q.size()) {
            int t = q.front();
            q.pop();
            for (auto e : edges[t]) {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
            ret.push_back(t);
        }
        // 判断是否入度全为0了
        if (ret.size() == n)
            return ret;
        else
            return {};
    }
};
//合唱队形
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int f[N], g[N], a[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (a[i] > a[j])
                f[i] = max(f[j] + 1, f[i]);
        }
    }
    for (int i = n; i >= 1; --i) {
        g[i] = 1;
        for (int j = n; j > i; --j) {
            if (a[i] > a[j])
                g[i] = max(g[j] + 1, g[i]);
        }
    }

    int ret = 0;
    for (int i = 1; i <= n; ++i)
        ret = max(f[i] + g[i] - 1, ret);
    cout << n - ret << endl;
    return 0;
}
//棋子翻转
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector<vector<>>
     * @param f int整型vector<vector<>>
     * @return int整型vector<vector<>>
     */
    using pii = pair<int, int>;
    vector<pii> co = { {0,1},{1,0},{0,-1},{-1,0} };
    vector<vector<int> > flipChess(vector<vector<int> >& A, vector<vector<int> >& f) {
        for (auto e : f) {
            int x = e[0] - 1;
            int y = e[1] - 1;
            for (auto p : co) {
                auto [a, b] = p;
                int dx = a + x;
                int dy = b + y;
                if (dx >= 0 && dx < 4 && dy >= 0 && dy < 4 && A[dx][dy] == 0)
                    A[dx][dy] = 1;
                else if (dx >= 0 && dx < 4 && dy >= 0 && dy < 4 && A[dx][dy] == 1)
                    A[dx][dy] = 0;
            }
        }
        return A;
    }
};
//宵暗的妖怪
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int main() {
    int n;
    cin >> n;
    vector<ll>arr(N);
    vector<ll>dp(N);
    for (int i = 1;i <= n;i++)
        cin >> arr[i];
    for (int i = 3;i <= n;i++) {
        dp[i] = max(dp[i - 1], dp[i - 3] + arr[i - 1]);
    }
    cout << dp[n] << endl;
    return 0;
}
//过桥
#include <iostream>
using namespace std;
const int N = 2010;
int n;
int arr[N];
int bfs() {
    int left = 1, right = 1;
    int ret = 0;
    while (left <= right) {
        ret++;
        int r = right;
        for (int i = left; i <= right; i++) {
            r = max(r, arr[i] + i);
            if (r >= n) {
                return ret;
            }
        }
        left = right + 1;
        right = r;
    }
    return -1;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    cout << bfs() << endl;

    return 0;
}
//最大差值
#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        int ret = INT_MIN;
        int l = 0, r = 1;
        while (r < n) {
            ret = max(A[r] - A[l], ret);
            if (A[r] < A[l]) {
                l = r;
            }
            r++;
        }
        return ret < 0 ? 0 : ret;
    }
};
//兑换零钱
#include <climits>
#include <cstring>
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
    int n, aim;
    cin >> n >> aim;
    vector<int>arr(n);
    int dp[5010];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    // sort(arr.begin(), arr.end(), [](int a, int b) {
    //     return a > b;
    // });
    memset(dp, 0x3f3f3f, sizeof(dp));
    dp[0] = 0;
    //int ret = 0;
//     for(int i = 0;i < n;i++){
//         while(arr[i] <= aim){
//             aim -= arr[i];
//             ret++;
//         }
//         if(aim == 0)
//             break;
//     }
//     if(aim == 0)
//         cout<<ret<<endl;
//     else
//         cout<< -1<<endl;
//     return 0;
// }
    for (int i = 0; i < n; i++) {
        for (int j = arr[i]; j <= aim; j++)
            dp[j] = min(dp[j], dp[j - arr[i]] + 1);
    }
    cout << (dp[aim] == 0x3f3f3f ? -1 : dp[aim]) << endl;
    return 0;
}
//小红的子串
#include <iostream>
#include <cstring>
using ll = long long;
using namespace std;

int n, l, r;
char s[200010];

ll find(int x) {
    if (x == 0)
        return 0;
    ll cnt[26] = { 0 };
    ll kind = 0, ret = 0;
    int L = 1, R = 1;
    while (R <= n) {
        if (cnt[s[R] - 'a']++ == 0)
            kind++;

        while (kind > x) {
            if (cnt[s[L++] - 'a']-- == 1)
                kind--;
        }

        ret += R - L + 1;
        R++;
    }
    return ret;
}
int main() {
    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i)
        cin >> s[i];

    cout << find(r) - find(l - 1) << endl;
    return 0;
}
//kotori和抽卡（二）
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    double ret = 1;
    for (int i = 1;i <= n - m;i++) {
        ret *= 0.2 * (n - i + 1) / i;
    }
    for (int i = 0;i < m;i++) {
        ret *= 0.8;
    }
    printf("%.4lf", ret);
    return 0;
}
//rudy和薯条
//排序 + 前缀和 + 滑动窗⼝
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, l, r;
int arr[N];
// 找出差值在 [0, x] 之间⼀共有多少对
long long find(int x) {
    int left = 0, right = 0;
    long long ret = 0;
    while (right < n) {
        while (arr[right] - arr[left] > x) left++;
        ret += right - left;
        right++;
    }
    return ret;
}
int main() {
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);

    cout << find(r) - find(l - 1) << endl;

    return 0;
}
//循环汉诺塔
#include <iostream>
using namespace std;
const int MO = 1e9 + 7;
int n;
int main() {
    cin >> n;
    int x = 1, y = 2;
    for (int i = 2;i <= n;i++) {
        int tmp_x = x, tmp_y = y;
        x = (2 * tmp_y + 1) % MO;
        y = ((2 * tmp_y) % MO + 2 + tmp_x) % MO;
    }
    cout << x << " " << y << endl;
    return 0;
}
//差值
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int n;
int main() {
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0;i < n;i++)cin >> arr[i];
    sort(arr.begin(), arr.end());
    ll ret = LONG_LONG_MAX;
    int r = 1, l = 0;
    while (r < n) {
        ret = min(ret, arr[r] - arr[l]);
        r++;
        l++;
    }
    cout << ret << endl;
    return 0;
}
//kotori和素因子
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, a[1005], vis[1005], ans = inf;
vector<int> f[15];
void dfs(int n, int sum) {
    if (ans <= sum) {
        return;
    }
    if (n == 0) {
        ans = sum;
    }
    else {
        for (int i = 0; i < f[n].size(); i++) {
            if (!vis[f[n][i]]) {
                vis[f[n][i]] = 1;
                dfs(n - 1, sum + f[n][i]);
                vis[f[n][i]] = 0;
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        int m = a[i];
        for (int j = 2; j <= m / j; j++) {
            if (m % j == 0) {
                f[i].push_back(j);
                while (!(m % j)) {
                    m /= j;
                }
            }
        }
        if (m > 1) {
            f[i].push_back(m);
        }
    }
    dfs(n, 0);
    if (ans == inf) {
        cout << -1 << endl;
    }
    else {
        cout << ans << endl;
    }
    return 0;
}
//dd爱科学1.0
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, a[1005], vis[1005], ans = inf;
vector<int> f[15];
void dfs(int n, int sum) {
    if (ans <= sum) {
        return;
    }
    if (n == 0) {
        ans = sum;
    }
    else {
        for (int i = 0; i < f[n].size(); i++) {
            if (!vis[f[n][i]]) {
                vis[f[n][i]] = 1;
                dfs(n - 1, sum + f[n][i]);
                vis[f[n][i]] = 0;
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        int m = a[i];
        for (int j = 2; j <= m / j; j++) {
            if (m % j == 0) {
                f[i].push_back(j);
                while (!(m % j)) {
                    m /= j;
                }
            }
        }
        if (m > 1) {
            f[i].push_back(m);
        }
    }
    dfs(n, 0);
    if (ans == inf) {
        cout << -1 << endl;
    }
    else {
        cout << ans << endl;
    }
    return 0;
}
//kanan和高音
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0;i < n;i++)cin >> arr[i];
    int ret = 1;
    int len = 1;
    for (int i = 1;i < n;i++) {
        if (arr[i] - arr[i - 1] <= 8)
            len++;
        else
            len = 1;
        ret = max(len, ret);
    }
    cout << ret << endl;
    return 0;
}
//拜访
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        int x1, x2, y1, y2;
        vector<vector<int>>dp(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }
                if (CityMap[i][j] == 2) {
                    x2 = i;
                    y2 = j;
                }
            }
        }
        int dx = x1 < x2 ? 1 : -1;
        int dy = y1 < y2 ? 1 : -1;
        dp[x1][y1] = 1;
        for (int x = x1 + dx; x != x2 + dx; x += dx) {
            dp[x][y1] = CityMap[x][y1] != -1 ? dp[x - dx][y1] : 0;
            if (dp[x - dx][y1] == 0)
                dp[x][y1] = 1;
        }
        for (int y = y1 + dy; y != y2 + dy; y += dy) {
            dp[x1][y] = CityMap[x1][y] != -1 ? dp[x1][y - dy] : 0;
            if (dp[x1][y - dy] == 0)
                dp[x1][y] = 1;
        }
        for (int x = x1 + dx; x != x2 + dx; x += dx) {
            for (int y = y1 + dy; y != y2 + dy; y += dy) {
                dp[x][y] = CityMap[x][y] != -1 ? dp[x - dx][y] + dp[x][y - dy] : 0;
            }
        }
        return dp[x2][y2];
    }
};
//买卖股票的最好时机（四）
#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> dp(k, vector<int>(2));
    int v;
    scanf("%d", &v);
    for (int i = 0; i < k; ++i) {
        dp[i][0] = -v;
        dp[i][1] = 0;
    }
    for (int i = 1; i < n; ++i) {
        scanf("%d", &v);
        dp[0][0] = max(dp[0][0], -v);
        dp[0][1] = max(dp[0][1], dp[0][0] + v);
        for (int j = 1; j < k; ++j) {
            dp[j][0] = max(dp[j - 1][1] - v, dp[j][0]);
            dp[j][1] = max(dp[j][1], dp[j][0] + v);
        }
    }
    cout << dp[k - 1][1] << endl;
    return 0;
}
//AOE还是单体？
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
using ll = long long;
int main() {
    ll n, x;
    cin >> n >> x;
    vector<ll>a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    sort(a.begin(), a.end());
    ll ret = 0;
    if (x >= n) {
        for (int i = 0; i < n; i++)
            ret += a[i];
    }
    else {
        ll t, sum = 0;
        t = (n - x) * x;
        for (int i = n - x;i < n;i++)
            sum += a[i] - (n - x);
        ret = sum + t;
    }
    cout << ret << endl;
    return 0;
}
//kotori和n皇后
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
map<int, bool> a, b, c, r;
int main(void) {
    int k, x, y, t, idx = INF, i;
    cin >> k;
    for (i = 1; i <= k; i++) {
        cin >> x >> y;
        if (idx != INF)
            continue;
        if (!a[x - y] && !b[x + y] && !c[x] && !r[y])
            a[x - y] = b[x + y] = c[x] = r[y] = 1;
        else
            idx = i;
    }
    cin >> t;
    while (t--) {
        cin >> i;
        if (i >= idx)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}
//取金币
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param coins int整型vector
     * @return int整型
     */
    int arr[110] = { 0 };
    int dp[110][110] = { 0 };
    int getCoins(vector<int>& coins) {
        int n = coins.size();
        arr[0] = arr[n + 1] = 1;
        for (int i = 1;i <= n;i++) {
            arr[i] = coins[i - 1];
        }
        for (int i = n;i >= 1;i--)
            for (int j = i;j <= n;j++)
                for (int k = i;k <= j;k++)
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
        return dp[1][n];
    }

};
//矩阵转置
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++)
            cout << arr[i][j] << " ";
        cout << endl;
    }
    return 0;
}
//四个选项
#include <iostream>
#include <vector>
using namespace std;
int p[4];
int fa[20];
int t[20];
int ans = 0;
int findParent(int x) {
    if (fa[x] != x)
        fa[x] = findParent(fa[x]);

    return fa[x];
}
void dfs(int x) {
    if (x == 13) {
        ans++;
        return;
    }
    if (t[x] == 0)
        dfs(x + 1);
    else {
        for (int i = 0; i < 4; i++)
            if (t[x] <= p[i]) {
                p[i] -= t[x];
                dfs(x + 1);
                p[i] += t[x];
            }
    }
}
int main() {
    for (int i = 1; i <= 12; i++)
        fa[i] = i;

    int m, x, y;
    cin >> p[0] >> p[1] >> p[2] >> p[3] >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        int fx = findParent(x), fy = findParent(y);
        if (fx != fy)
            fa[fx] = fy;
    }
    for (int i = 1; i <= 12; i++)
        t[findParent(i)]++;
    dfs(1);
    cout << ans << endl;
    return 0;
}
//接雨水问题
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        long long ret = 0;
        int l = 0, r = arr.size() - 1;
        int lmax = 0, rmax = 0;
        while (l < r) {
            lmax = max(lmax, arr[l]);
            rmax = max(rmax, arr[r]);
            if (arr[l] < arr[r]) {
                ret += lmax - arr[l];
                l++;
            }
            else {
                ret += rmax - arr[r];
                r--;
            }
        }
        return ret;
    }
};
//疯狂的自我检索者
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int>arr(n - m);
    for (int i = 0;i < n - m;i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    int sum = accumulate(arr.begin(), arr.end(), 0);
    cout << (sum + m) * 1.00000 / n << " ";
    cout << (sum + 5 * m) * 1.00000 / n << " ";
    return 0;
}
//栈和排序
#include <stack>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        int n = a.size();
        vector<bool>mp(n + 1, false);
        vector<int>ret;
        stack<int> q;
        for (int i : a) {
            mp[i] = true;
            q.push(i);
            while (mp[n])n--;
            while (!q.empty() && q.top() > n) {
                ret.push_back(q.top());
                q.pop();
            }
        }
        return ret;
    }
};
//加减
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

long long solve(int l, int r, vector<ll> a, vector<ll> s) {
    int mid = (l + r) >> 1;//中间值肯定是最多次数元素
    return s[r] - s[mid] - s[mid - 1] + s[l - 1] - a[mid] * (r - mid) + a[mid] * (mid - l);
    /*s[mid+1-r]-s[l-mid]-中间数*(右边数量)+中间数*(左边数)==
    s[mid+1-r]-中间数*(右边数量)+中间数*(左边数)-s[l-mid]==
    l到中间数的变化次数+中间数到r的变化次数==总变化次数*/
}
int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll>arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    vector<ll>s(n);
    s[0] = arr[0];
    for (int i = 1; i < n; i++) {
        s[i] = s[i - 1] + arr[i];
    }
    int ret = 0;
    for (int i = 0; i < n; i++) {
        int l = i, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (solve(i, mid, arr, s) <= k) {
                l = mid + 1;
                ret = max(ret, mid - i + 1);
            }
            else {
                r = mid - 1;
            }
        }
    }
    cout << ret << endl;
    return 0;
}